﻿// ReSharper disable ArrangeThisQualifier

using System.Diagnostics;

namespace KinonekoSoftware.Extensions.Collections.BST
{
    public partial class BinaryTreeCollection<TKey, TValue> : ICollection<TValue> where TKey : IComparable<TKey>
    {
        private readonly Func<TValue, TKey> _selector;
        protected        Node               Root;
        private          int                _count;
        private          int                _version;
        private          byte               _height;

        [DebuggerDisplay("{Key},{Value}")]
        public sealed class Node
        {
            public Node Parent;
            public Node Left;
            public Node Right;

            public TKey   Key;
            public TValue Value;


            public Node Successor
            {
                get
                {
                    // 后继节点：
                    // 比当前节点值大，但是是所有比当前节点值大的节点中，最小的。
                    //
                    if (Right is not null)
                    {
                        var x = Right;

                        while (x?.Left != null)
                        {
                            x = x.Left;
                        }

                        return x;
                    }


                    var parent = Parent;
                    var self   = this;

                    while (parent is not null && parent.Left != self)
                    {
                        self   = parent;
                        parent = parent.Parent;
                    }

                    return parent;
                }
            }

            public Node Precusors
            {
                get
                {
                    // 前驱节点：
                    // 比当前节点值大，且是所有比当前节点值大的节点中，最大的。
                    //
                    // 后继节点：
                    // 比当前节点值大，但是是所有比当前节点值大的节点中，最小的。
                    //
                    if (Right is not null)
                    {
                        var x = Right;

                        while (x?.Right != null)
                        {
                            x = x.Right;
                        }

                        return x;
                    }



                    var parent = Parent;
                    var self   = this;

                    while (parent is not null && parent.Right != self)
                    {
                        self   = parent;
                        parent = parent.Parent;
                    }

                    return parent;
                }
            }

            public void Rebalance()
            {
                while (Math.Abs(Balance) > 1)
                {
                    if (Balance < 0)
                    {
                        if (Left.Balance > 0)
                        {
                            // lr
                            Left.RotateLeft();
                        }

                        // ll
                        RotateRight();
                    }
                    else
                    {
                        if (Right.Balance < 0)
                        {
                            // rl
                            Right.RotateRight();
                        }

                        //
                        // rr
                        RotateLeft();
                    }
                }
            }

            public void RotateLeft()
            {
                /* Rotate tree to the left
                 *
                 *       this               this
                 *       /  \               /  \
                 *      A   right   ===>  left  C
                 *           / \          / \
                 *          B   C        A   B
                 */

                var a     = Left;
                var right = Right;
                var b     = right.Left;
                var c     = right.Right;
                var key   = this.Key;
                var value = this.Value;

                //
                // 交换this和right的数据
                this.Key    = right.Key;
                this.Value  = right.Value;
                right.Value = value;
                right.Key   = key;

                //
                // 配置this的新结构
                this.Left  = right;
                this.Right = c;

                //
                // 配置right的新结构
                right.Left  = a;
                right.Right = b;

                //
                // 保证b，c的高度一致
                if (b is not null) b.Height = (byte)(right.Height + 1);
                if (c is not null) c.Height = (byte)(right.Height + 1);

            }

            public void RotateRight()
            {
                /* Rotate tree to the right
                 *
                 *       this             this
                 *       /  \             /  \
                 *     left  C   ===>    A  right
                 *     / \                   /  \
                 *    A   B                 B    C
                 */

                var left  = Left;
                var c     = Right;
                var a     = left.Left;
                var b     = left.Right;
                var key   = this.Key;
                var value = this.Value;

                //
                // 交换this和right的数据
                this.Key   = left.Key;
                this.Value = left.Value;
                left.Value = value;
                left.Key   = key;

                //
                // 配置this的新结构
                this.Left  = a;
                this.Right = left;

                left.Left  = b;
                left.Right = c;

                //
                // 保证b，c的高度一致
                if (b is not null) b.Height = (byte)(left.Height + 1);
                if (c is not null) c.Height = (byte)(left.Height + 1);
            }

            public byte Height  { get; set; }
            public int  Balance => (Right?.Height ?? Height) - (Left?.Height ?? Height);
            public bool IsLeaf  => Right is null && Left is null;

        }
        

        public BinaryTreeCollection(Func<TValue, TKey> selector)
        {
            _selector = selector ?? throw new ArgumentNullException(nameof(selector));
        }


        #region GetNode

        public Node GetNode(TValue content)
        {
            if (Root is null)
            {
                return null;
            }

            return GetNode(Root, content);
        }

        public Node GetNode(TKey value)
        {
            if (Root is null)
            {
                return null;
            }

            return GetNode(Root, value);
        }

        private Node GetNode(Node node, TValue content)
        {
            while (true)
            {
                var result = Comparer<TKey>.Default.Compare(node.Key, _selector(content));

                if (result == 0)
                {
                    return node;
                }

                if (result < 0)
                {
                    if (node.Right is null)
                    {
                        return null;
                    }

                    node = node.Right;
                    continue;
                }


                if (node.Left is null)
                {
                    return null;
                }

                node = node.Left;
            }
        }

        private static Node GetNode(Node node, TKey key)
        {
            while (true)
            {
                var result = Comparer<TKey>.Default.Compare(node.Key, key);

                if (result == 0)
                {
                    return node;
                }

                if (result < 0)
                {
                    if (node.Right is null)
                    {
                        return null;
                    }

                    node = node.Right;
                    continue;
                }


                if (node.Left is null)
                {
                    return null;
                }

                node = node.Left;
            }
        }

        #endregion

        protected int Version
        {
            get => _version;
            set => _version = value;
        }

        public event InsertValueDuplicatedHandler<TKey, TValue> DuplicatedWhenInsertValue;

        public byte Height => _height;
        public int  Count  => _count;
    }


    public delegate bool InsertValueDuplicatedHandler<TKey, TValue>(BinaryTreeCollection<TKey, TValue>.Node newValue, TValue other, TValue current) where TKey : IComparable<TKey>;

    public delegate bool ChangeValueDuplicatedHandler<TKey, TValue>(TKey newValue, TValue other, TValue current) where TKey : IComparable<TKey>;
}